package sol.leetcode;

/**
 * Search Insert Position
 */
public class Issue035 {
    public int searchInsert(int[] nums, int target) {
        int len = nums.length;
        int l = 0, r = len - 1, m;
        while (l <= r) {
            m = (l + r) / 2;
            if (nums[m] == target)
                return m;
            else if (nums[m] > target) {
                r = m - 1;
                if (r < 0)
                    return 0;
            } else {
                l = m + 1;
                if (l > len - 1)
                    return len;
            }
        }
        return target > nums[l] ? l + 1 : l;
    }

    public static void main(String[] args) {
        int[] nums = {1, 3, 5, 6};
        System.out.println(new Issue035().searchInsert(nums, 9));
    }
}
